{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "04d57ea5-7a1d-4c7f-8aaf-4f0c6bbc8a35",
   "metadata": {},
   "source": [
    "# 量子运算器线路\n",
    "\n",
    "[![下载Notebook](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/website-images/master/resource/_static/logo_notebook.png)](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/notebook/master/mindquantum/zh_cn/quantum_arithmetic_circuit.ipynb)&emsp;\n",
    "[![下载样例代码](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/website-images/master/resource/_static/logo_download_code.png)](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/notebook/master/mindquantum/zh_cn/quantum_arithmetic_circuit.py)&emsp;\n",
    "[![查看源文件](https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/website-images/master/resource/_static/logo_source.png)](https://gitee.com/mindspore/docs/blob/master/docs/mindquantum/docs/source_zh_cn/quantum_arithmetic_circuit.ipynb)\n",
    "\n",
    "## 背景介绍\n",
    "\n",
    "量子计算中一个最有影响力的量子算法就是Shor算法，它能指数加速大整数分解并对广泛使用的RSA加密算法造成巨大威胁。Shor算法中最关键的一个结构为模幂线路。Vedral、Barenco和Ekert（VBE）最早提出如何构建量子线路实现模幂等数值运算，下面介绍并实现VBE线路。\n",
    "\n",
    "本教程主要参考论文 [H. T. Larasati and H. Kim, \"Simulation of Modular Exponentiation Circuit for Shor's Algorithm in Qiskit, 2020](https://ieeexplore.ieee.org/document/9310794) 实现。\n",
    "\n",
    "## 内容概要\n",
    "\n",
    "本教程将使用MindQuantum量子计算框架实现加法器、减法器、模加法器、模乘法器和模指数器等模块化线路功能。它们之间有递进关系：模加法器基于加法器实现，模乘法器基于模加法器实现，模指数器基于模乘法器实现。具体而言，构建模幂线路步骤如下：\n",
    "\n",
    "* 加法器，输入 $a, b \\ge 0$，输出 $a+b$；\n",
    "* 模加法器，输出 $(a + b) mod N$；\n",
    "* 模乘法器，输出 $a x mod N$；\n",
    "* 模指数器，输出 $a^x mod N$。\n",
    "\n",
    "说明：“指数”和“幂”意思相同，有的地方可能混用。\n",
    "\n",
    "## 运算器\n",
    "\n",
    "### 加法器与减法器\n",
    "\n",
    "为了保持和论文一致，所引用图片按照原来编号。VBE加法器(adder)原理如 `Fig.1` 所示，通过量子线路实现 $|a, b\\rangle \\rightarrow |a, a+b\\rangle$，包含一个进位。把存储数值a的寄存器叫做寄存器A，存储b的寄存器叫做寄存器B。分析图1所示的线路，对 $n$ 位的加法运算，总共需要 $3n+1$ 个量子比特，最终的结果存储在寄存器 S($s_3 s_2 s_1 s_0$)。图中框住的 CARRY、SUM、Reverse CARRY分别用于计算进位、求和、取消进位，本质上都是将二进制运算转换成量子受控门线路。例如第1个CARRY，如果 $a_0, b_0$ 均是1，则其进位（图中的从上往下第4条线）通过受控CNOT门实现进位。\n",
    "\n",
    "<img src=\"images/Fig1_3bit_adder.jpg\" width=600>\n",
    "\n",
    "针对 4-bit 线路也可以按此方法实现，具体线路如 `Fig.6` 所示。减法是加法的逆运算，可直接将加法器线路逆转得到减法器（subtractor），减法器也叫做逆加法器（reversed-adder）。模减法器实现 $|a, b\\rangle \\rightarrow |a, b-a\\rangle$。 `Fig.7` 展示了减法器线路。\n",
    "\n",
    "<img src=\"images/Fig6_adder.jpg\" width=600>\n",
    "\n",
    "<img src=\"images/Fig7_subtractor.jpg\" width=600>\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "828b41f0-9987-4083-9883-8ac395fc6ba5",
   "metadata": {},
   "source": [
    "下面使用 MindQuantum 实现 `Fig.6` 和 `Fig.7` 的加法器和减法器。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8c15251b-44d1-4168-86f4-02a5593b7fed",
   "metadata": {},
   "outputs": [],
   "source": [
    "from mindquantum.core.gates import X, SWAP\n",
    "from mindquantum.core.circuit import Circuit, shift, UN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a7771058-a7f8-474a-bf9d-cf5f30797ee3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Adder() -> Circuit:\n",
    "    \"\"\"4-bit 加法器，对应 Fig.6\n",
    "    \"\"\"\n",
    "    return Circuit([\n",
    "        X(10, [4, 0]),\n",
    "        X(11, [5, 1]),\n",
    "        X(12, [6, 2]),\n",
    "        X(8, [7, 3]),\n",
    "        X(4, 0),\n",
    "        X(5, 1),\n",
    "        X(6, 2),\n",
    "        X(7, 3),\n",
    "        X(10, [9, 4]),\n",
    "        X(11, [10, 5]),\n",
    "        X(12, [11, 6]),\n",
    "        X(8, [7, 12]),\n",
    "        X(7, 12),\n",
    "        X(12, [11, 6]),\n",
    "        X(6, 2),\n",
    "        X(12, [6, 2]),\n",
    "        X(6, 2),\n",
    "        X(6, 11),\n",
    "        X(11, [10, 5]),\n",
    "        X(5, 1),\n",
    "        X(11, [5, 1]),\n",
    "        X(5, 1),\n",
    "        X(5, 10),\n",
    "        X(10, [9, 4]),\n",
    "        X(4, 0),\n",
    "        X(10, [4, 0]),\n",
    "        X(4, 0),\n",
    "        X(4, 9)\n",
    "    ])\n",
    "\n",
    "\n",
    "def AdderRev() -> Circuit:\n",
    "    \"\"\"4-bit 逆加法器（减法器），对应 Fig.7\n",
    "    \"\"\"\n",
    "    return Circuit([\n",
    "        X(4, 9),\n",
    "        X(4, 0),\n",
    "        X(10, [4, 0]),\n",
    "        X(4, 0),\n",
    "        X(10, [9, 4]),\n",
    "        X(5, 10),\n",
    "        X(5, 1),\n",
    "        X(11, [5, 1]),\n",
    "        X(5, 1),\n",
    "        X(11, [10, 5]),\n",
    "        X(6, 11),\n",
    "        X(6, 2),\n",
    "        X(12, [6, 2]),\n",
    "        X(6, 2),\n",
    "        X(12, [11, 6]),\n",
    "        X(7, 12),\n",
    "        X(8, [7, 12]),\n",
    "        X(7, 3),\n",
    "        X(12, [6, 2]),\n",
    "        X(8, [7, 3]),\n",
    "        X(6, 2),\n",
    "        X(12, [11, 6]),\n",
    "        X(11, [5, 1]),\n",
    "        X(5, 1),\n",
    "        X(11, [10, 5]),\n",
    "        X(10, [4, 0]),\n",
    "        X(4, 0),\n",
    "        X(10, [9, 4])\n",
    "    ])"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "edcf41e3-8223-40fe-9e47-381a6a693f81",
   "metadata": {},
   "source": [
    "逆加法器（减法器）也可以直接通过 MindQuantum 的 `reverse()` 函数实现，例如：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ca21247b-ee5f-47ae-b990-f98ddb910c95",
   "metadata": {},
   "outputs": [],
   "source": [
    "def AdderRev2() -> Circuit:\n",
    "    \"\"\"逆-加法器\"\"\"\n",
    "    cir = Adder()\n",
    "    cir.reverse()\n",
    "    return cir"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "baf7effe-8549-4d77-87f9-7681e27c9e3c",
   "metadata": {},
   "source": [
    "为了便于演示，定义函数 `c2q(...)` 和 `q2c(...)` ，分别将经典数值转换成量子线路、读取量子线路状态并转换成经典数值。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c390dd43-e4f1-4cbb-9d1e-d55996aaaa23",
   "metadata": {},
   "outputs": [],
   "source": [
    "def c2q(qlist: list, value: int) -> Circuit:\n",
    "    \"\"\"将经典计算机数字转换成量子线路\n",
    "    Args:\n",
    "        qlist:  list[int]: 作用的qubit，低位在后，如 [3,2,1,0]\n",
    "        value:  int:       十进制的加数或减数，非负\n",
    "    Return:\n",
    "        准备了初态的线路\n",
    "    \"\"\"\n",
    "    vbin = bin(value)[2:][::-1]   # 将十进制转换成二进制，并且低位在前\n",
    "    qlist = qlist[::-1]           # 低位在前\n",
    "    cir = Circuit([X.on(q) for q, v in zip(qlist, vbin) if v == '1'])\n",
    "    return cir\n",
    "\n",
    "\n",
    "def q2c(cir: Circuit, qlist: list) -> int:\n",
    "    \"\"\"获取量子线路状态，并得到对应的经典数值\n",
    "    Args:\n",
    "        cir: 量子线路\n",
    "        qlist: 保存结果的量子位，对 [q2, q1, q0] 读取到的数为 int(q2q1q0)\n",
    "    Return:\n",
    "        十进制的量子态表示的数值\n",
    "    \"\"\"\n",
    "    ket_str = cir.get_qs(ket=True)   # 获取字符串表示的状态\n",
    "    print(f'ket string: {ket_str}')\n",
    "    # 解析字符串得到十进制的数值\n",
    "    res_str = \"\"\n",
    "    for q in qlist:\n",
    "        # |0101>，需要逆序和除去最后的ket符号\n",
    "        res_str += ket_str[-q-2]\n",
    "    return int(res_str, base=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b80cc48-1920-42b5-8ebc-2abb391f14e0",
   "metadata": {},
   "source": [
    "下面验证加法器和减法器，计算 $a=3, b=8, a+b=11, b-a=5$。验证代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6c99fda9-d153-4b53-bd73-11a82aa25b9e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "验证加法器,减法器:\n",
      "ket string: 1¦0000010110011⟩\n",
      "ket string: 1¦0010001010011⟩\n",
      "q_add = 11, c_add = 11\n",
      "q_sub = 5, c_sub = 5\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def demo1():\n",
    "    \"\"\"验证 Fig.6（加法器）, Fig.7 （减法器）\n",
    "    \"\"\"\n",
    "    print(\"验证加法器,减法器:\")\n",
    "    # 验证 b + a, b - a\n",
    "    a = 3\n",
    "    b = 8\n",
    "    cir_a = c2q([3, 2, 1, 0], a)   # 将数值 a 赋值在第3,2,1,0条量子比特线路上\n",
    "    cir_b = c2q([7, 6, 5, 4], b)\n",
    "\n",
    "    cir_add = cir_a + cir_b + Adder()\n",
    "    q_add = q2c(cir_add, [7, 6, 5, 4])  # 读取量子线缆结果并转换成经典数值\n",
    "\n",
    "    cir_sub = cir_a + cir_b + AdderRev()\n",
    "    q_sub = q2c(cir_sub, [7, 6, 5, 4])\n",
    "\n",
    "    print(\n",
    "        f\"q_add = {q_add}, c_add = {b + a}\\nq_sub = {q_sub}, c_sub = {b - a}\\n\")\n",
    "\n",
    "\n",
    "demo1()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "f19c0df8-8414-4ad9-a326-68a3f329ebf5",
   "metadata": {},
   "source": [
    "打印的结果中， `q_` 开头代表量子计算的结果， `c_` 开头代表经典计算机或正确的结果， `add` 和 `sub` 分别代表加法器和减法器， `ket string` 是线路的终态。以 a = 3, b = 8 为例，量子线路结果正确。\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "476ea679-1fab-4a70-b977-e24de570dc5c",
   "metadata": {},
   "source": [
    "### 模加法器\n",
    "\n",
    "模加法器实现 $|a, b\\rangle \\rightarrow |a, (a+b) mod N\\rangle$。当 $a+b < N$ 时，模加法器使用互补概念（如加法器与逆加法器）来检测比较。其实现如 `Fig.2` 。实现使用5个加法器（3个加法器和2个逆加法器），前两个加法器实现 $a+b-N$，判断其结果是否小于0，如果小于0，则再加上 $N$。最后两个加法器用于将 Temporary Qubit 的状态恢复到 $|0\\rangle$，在量子线路中，通常在计算完成后将辅助比特恢复至初始状态。模加结果存储在寄存器B中。\n",
    "\n",
    "<img src=\"images/Fig2_modular_adder.jpg\" width=600>\n",
    "\n",
    "一个 4-bit 的模加器具体实现如 `Fig.8` 所示。图中的不同灰色竖线无特殊作用，仅仅用于将线路划分成不同模块展示。输入和输出分别在最左和最右部分。\n",
    "\n",
    "<img src=\"images/Fig8_modular_adder.jpg\" width=600>\n",
    "\n",
    "模加法器及验证代码实现如下所示："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "32884490-89cd-4cd5-b530-e4214ae8ffdb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "验证模加法器:\n",
      "ket string: 1¦000000000001011011⟩\n",
      "q_add = 5, c_add = 5\n"
     ]
    }
   ],
   "source": [
    "def ModAdder() -> Circuit:\n",
    "    \"\"\"模加法器，对应 Fig.8\n",
    "    \"\"\"\n",
    "    cir = Circuit()\n",
    "    cir += Adder()\n",
    "    cir += UN(SWAP, maps_obj=[(0, 13), (1, 14), (2, 15), (3, 16)])\n",
    "    cir += AdderRev2()\n",
    "    cir += Circuit([X(8), X(17, 8), X(8)])\n",
    "    cir += UN(X, maps_obj=[0, 1, 2, 3], maps_ctrl=[17, 17, 17, 17])\n",
    "    cir += Adder()\n",
    "    cir += UN(X, maps_obj=[0, 1, 2, 3], maps_ctrl=[17, 17, 17, 17])\n",
    "    cir += UN(SWAP, maps_obj=[(0, 13), (1, 14), (2, 15), (3, 16)])\n",
    "    cir += AdderRev2()\n",
    "    cir += X(17, 8)\n",
    "    cir += Adder()\n",
    "    return cir\n",
    "\n",
    "\n",
    "def demo2():\n",
    "    \"\"\"验证模加法器\n",
    "    \"\"\"\n",
    "    print(\"验证模加法器:\")\n",
    "    # 1. 计算 (a + b) mod n\n",
    "    # 2. 计算 (b - a) mod n。注：对 b<a, (b-a) mod n = (b-a+n) mod n\n",
    "    a = 11\n",
    "    b = 9\n",
    "    n = 15\n",
    "    # 将经典数值转换成量子线路编码\n",
    "    cir_a = c2q([3, 2, 1, 0], a)\n",
    "    cir_b = c2q([7, 6, 5, 4], b)\n",
    "    cir_n = c2q([16, 15, 14, 13], n)  # 输入置1\n",
    "\n",
    "    cir_madd = cir_a + cir_b + cir_n + ModAdder() + cir_n\n",
    "    # 使用量子线路计算结果\n",
    "    q_add = q2c(cir_madd, [7, 6, 5, 4])\n",
    "    # 经典计算验证\n",
    "    c_add = (a + b) % n\n",
    "\n",
    "    print(f\"q_add = {q_add}, c_add = {c_add}\")\n",
    "\n",
    "\n",
    "demo2()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "eea29e0d-cc94-48f9-ab8c-8af6f6ed5a6c",
   "metadata": {},
   "source": [
    "## 模乘法器\n",
    "\n",
    "模乘法器实现 $|x, 0\\rangle \\rightarrow |x, ax mod N\\rangle$。其中添加了一个控制比特（$control_0$ 或 $|c\\rangle$），如果 $control_0 = 0$，则映射为 $|x, 0\\rangle \\rightarrow |x, x\\rangle$。由于\n",
    "\n",
    "$$\n",
    "ax = ax_{n-1} 2^{n-1} + \\cdots + a x_1 2^1 + a x_0 2^0\n",
    "$$\n",
    "\n",
    "依次将等号右侧的加法分别用模加法器实现，即可得乘法器，其结构原理如 `Fig.3` 所示。每个模加器 `Modadd` 模块通过一系列 Toffoli门赋值 $a2^i$，例如计算 $7x mod 15$，其中 $a=7$，$7\\times 2^0 mod 15 = 7, 7\\times 2^1 mod 15 = 14$，则在第1个 `Modadd` 的前后设置数值 7 相应的 Toffoli 门，其余依此类推。$n$ 位模乘法器需要 $6n+3$ 比特。输入位于的 $regx_0\\sim regx_3$，模数位于 $modulusN_0 \\sim modulusN_3$， `Fig.10` 中输入 $x=3$，模数 $N=15$。\n",
    "\n",
    "以 $7 x\\mod 15$ 为例，其线路如 Fig.10 所示。在 8U32G 硬件平台上，运行模乘法器耗时大约 20 秒。\n",
    "\n",
    "<img src=\"images/Fig3_moduler_multiplier.jpg\" width=600>\n",
    "\n",
    "<img src=\"images/Fig10_7xmod15.jpg\" width=600>\n",
    "\n",
    "实现模乘器的代码如下：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "c52790ba-df85-4a5d-9acc-cc2c14260a47",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "验证模乘法器(8U32G硬件大约耗时20秒):\n",
      "ket string: 1¦00000000000011000010011⟩\n",
      "q_mul = 3, c_mul = 3\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def ModMulti7xmod15():\n",
    "    \"\"\"4-bit 模乘法器，求 7x mod 15. 对应 Fig.10\n",
    "    \"\"\"\n",
    "    ns = 5  # 模加法器所需 shift 量\n",
    "    cir = Circuit()\n",
    "    cir += UN(X, maps_obj=[5, 6, 7], maps_ctrl=[[0, 1], [0, 1], [0, 1]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 6, 7], maps_ctrl=[[0, 1], [0, 1], [0, 1]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[6, 7, 8], maps_ctrl=[[0, 2], [0, 2], [0, 2]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[6, 7, 8], maps_ctrl=[[0, 2], [0, 2], [0, 2]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[5, 7, 8], maps_ctrl=[[0, 3], [0, 3], [0, 3]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 7, 8], maps_ctrl=[[0, 3], [0, 3], [0, 3]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[5, 6, 8], maps_ctrl=[[0, 4], [0, 4], [0, 4]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 6, 8], maps_ctrl=[[0, 4], [0, 4], [0, 4]])\n",
    "\n",
    "    cir += X(0)\n",
    "    cir += UN(X, maps_obj=[9, 10, 11, 12],\n",
    "              maps_ctrl=[[0, 1], [0, 2], [0, 3], [0, 4]])\n",
    "    cir += X(0)\n",
    "    return cir\n",
    "\n",
    "\n",
    "def demo3():\n",
    "    \"\"\"验证模乘法器\n",
    "    \"\"\"\n",
    "    print(\"验证模乘法器(8U32G硬件大约耗时20秒):\")\n",
    "    # 计算 7x mod n\n",
    "    ctrl = 1  # 控制位\n",
    "    x = 9\n",
    "    n = 15\n",
    "    cir_ctrl = c2q([0], ctrl)\n",
    "    cir_x = c2q([4, 3, 2, 1], x)\n",
    "    cir_n = c2q([21, 20, 19, 18], n)\n",
    "    cir_7x = cir_ctrl + cir_x + cir_n + ModMulti7xmod15() + cir_n\n",
    "    # 获取终态得到结果\n",
    "    q_mul = q2c(cir_7x, [12, 11, 10, 9])\n",
    "    c_mul = (7 * x) % 15\n",
    "\n",
    "    print(f\"q_mul = {q_mul}, c_mul = {c_mul}\\n\")\n",
    "\n",
    "\n",
    "demo3()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "9e59ed29-0158-4b72-adfa-e6d09af10a99",
   "metadata": {},
   "source": [
    "## 模指数器\n",
    "\n",
    "模指数器实现 $|x, 1, 0\\rangle = |x, a^x mod N, 0\\rangle$，中间的一些 $|0\\rangle$ 位为辅助比特。下面分析器数学原理，将 $a$ 和 $x$ 使用二进制表达，即\n",
    "\n",
    "$$\n",
    "a = a_{n-1} 2^{n-1} +\\cdots + a_1 2 + a_0\n",
    "$$\n",
    "\n",
    "$$\n",
    "x = x_{n-1} 2^{n-1} +\\cdots + x_1 2 + x_0\n",
    "$$\n",
    "\n",
    "则\n",
    "\n",
    "$$\n",
    "a^x = a^{x_{n-1}2^{n-1}} \\times \\cdots\\times a^{x_1 2}\\times a^{x_0}\n",
    "$$\n",
    "\n",
    "因此可以将模指数器使用一系列乘法器实现。VBE提出如 `Fig.4` 所示的量子线路，该线路由一系列模乘法器对组成（在每个对里面，其中一个是另一个的逆线路），通过使用交换门（SWAP）保存中间结果。逆线路用于取消计算（uncomputation）乘法结果，为下一个比特的乘法做准备。所谓的逆线路，其实用到模逆元，当两个数 $a, b$ 满足 $ab\\equiv 1 mod N$时，$a, b$互为模逆元，如 7, 13 关于模 15 互为模逆元。逆元线路首先实现逆元的线路，再通过 `reverse` 将线路左右翻转。\n",
    "\n",
    "<img src=\"images/Fig4_modular_exp.jpg\" width=600>\n",
    "\n",
    "`Fig.12` 是 4-bit 模指数器 $7^x mod 15$ 的具体实现，输入位于 $regx_e xp_0 \\sim regx_e xp_3$，最终的计算结果存储在 $regx_0 \\sim regx_3$ 中。以为例具体计算，其中 $7^{2^0} mod 15 = 7^1 mod 15 = 7$，$7^{2^1} mod 15 = 4$，$7^{2^2} mod 15 = 1, 7^{2^3} mod 15 = 1$，这4个数字的逆元依次为 $13, 4, 1, 1$，这也是 `Fig.12` 各个乘法器的数值的来源。\n",
    "\n",
    "<img src=\"images/Fig12_modular_exp.jpg\" width=800>\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "e95fe6d5-eb72-49a0-9fb8-c2ba0938dc4e",
   "metadata": {},
   "source": [
    "依次实现该4个数值的乘法器及对应的逆元线路。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "346c5ddb-e40e-4611-ab4d-cd112351d28d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ModMulti4xmod15():\n",
    "    \"\"\"4-bit 模乘法器，求 4x mod 15.\n",
    "    \"\"\"\n",
    "    ns = 5  # 模加法器所需 shift 量\n",
    "    cir = Circuit()\n",
    "    # ModAdd() 两边为 a2^i, a=4此处\n",
    "    cir += UN(X, maps_obj=[7], maps_ctrl=[[0, 1]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[7, 8], maps_ctrl=[[0, 1], [0, 2]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[8, 5], maps_ctrl=[[0, 2], [0, 3]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 6], maps_ctrl=[[0, 3], [0, 4]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[6], maps_ctrl=[[0, 4]])\n",
    "    cir += X(0)\n",
    "    cir += UN(X, maps_obj=[9, 10, 11, 12],\n",
    "              maps_ctrl=[[0, 1], [0, 2], [0, 3], [0, 4]])\n",
    "    cir += X(0)\n",
    "    return cir\n",
    "\n",
    "\n",
    "def ModMulti1xmod15(ns=5):\n",
    "    \"\"\"4-bit 模乘法器，求 1x mod 15.\"\"\"\n",
    "    ns = 5  # 模加法器所需 shift 量\n",
    "    cir = Circuit()\n",
    "    cir += UN(X, maps_obj=[5], maps_ctrl=[[0, 1]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 6], maps_ctrl=[[0, 1], [0, 2]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[6, 7], maps_ctrl=[[0, 2], [0, 3]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[7, 8], maps_ctrl=[[0, 3], [0, 4]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[8], maps_ctrl=[[0, 4]])\n",
    "    cir += X(0)\n",
    "    cir += UN(X, maps_obj=[9, 10, 11, 12],\n",
    "              maps_ctrl=[[0, 1], [0, 2], [0, 3], [0, 4]])\n",
    "    cir += X(0)\n",
    "    return cir\n",
    "\n",
    "\n",
    "def ModMulti13xmod15():\n",
    "    \"\"\"4-bit 模乘法器，求 13x mod 15.\n",
    "    \"\"\"\n",
    "    ns = 5  # 模加法器所需 shift 量\n",
    "    cir = Circuit()\n",
    "    cir += UN(X, maps_obj=[5, 7, 8], maps_ctrl=[[0, 1], [0, 1], [0, 1]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 7, 8], maps_ctrl=[[0, 1], [0, 1], [0, 1]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[5, 6, 8], maps_ctrl=[[0, 2], [0, 2], [0, 2]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 6, 8], maps_ctrl=[[0, 2], [0, 2], [0, 2]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[5, 6, 7], maps_ctrl=[[0, 3], [0, 3], [0, 3]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 6, 7], maps_ctrl=[[0, 3], [0, 3], [0, 3]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[6, 7, 8], maps_ctrl=[[0, 4], [0, 4], [0, 4]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[6, 7, 8], maps_ctrl=[[0, 4], [0, 4], [0, 4]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[8], maps_ctrl=[[0, 4]])\n",
    "    cir += X(0)\n",
    "    cir += UN(X, maps_obj=[9, 10, 11, 12],\n",
    "              maps_ctrl=[[0, 1], [0, 2], [0, 3], [0, 4]])\n",
    "    cir += X(0)\n",
    "    return cir\n",
    "\n",
    "\n",
    "def ModMulti4xmod15Rev():\n",
    "    \"\"\"将 4x mod 15 线路翻转\n",
    "    \"\"\"\n",
    "    cir = ModMulti4xmod15()\n",
    "    cir.reverse()\n",
    "    return cir\n",
    "\n",
    "\n",
    "def ModMulti1xmod15Rev():\n",
    "    \"\"\"将 1x mod 15 线路翻转\n",
    "    \"\"\"\n",
    "    cir = ModMulti1xmod15()\n",
    "    cir.reverse()\n",
    "    return cir\n",
    "\n",
    "\n",
    "def ModMulti13xmod15Rev():\n",
    "    \"\"\"将 13x mod 15 线路翻转\n",
    "    \"\"\"\n",
    "    cir = ModMulti13xmod15()\n",
    "    cir.reverse()\n",
    "    return cir\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "8935b9af-3d6b-4888-aa89-a921e444b71f",
   "metadata": {},
   "source": [
    "最终按照 `Fig.12` 实现 $7^a mod 15$，模指数器，并取 $a=3$ 验证结果。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8ddbd59a-c7f2-4466-9cf0-1913437fffe7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ModExp():\n",
    "    \"\"\"4-bit 模指数线路，对应 Fig.12\n",
    "    \"\"\"\n",
    "    ns = 4\n",
    "    cir = Circuit()\n",
    "    cir += X(4, 0)\n",
    "    cir += X(5)\n",
    "    cir += shift(ModMulti7xmod15(), ns)\n",
    "    cir += UN(SWAP, maps_obj=[(5, 13), (6, 14), (7, 15), (8, 16)])\n",
    "    cir += shift(ModMulti13xmod15Rev(), ns)\n",
    "\n",
    "    cir += UN(X, maps_obj=[4, 4], maps_ctrl=[0, 1])\n",
    "    cir += shift(ModMulti4xmod15(), ns)\n",
    "    cir += UN(SWAP, maps_obj=[(5, 13), (6, 14), (7, 15), (8, 16)])\n",
    "    cir += shift(ModMulti4xmod15Rev(), ns)\n",
    "\n",
    "    cir += UN(X, maps_obj=[4, 4], maps_ctrl=[1, 2])\n",
    "    cir += shift(ModMulti1xmod15(), ns)\n",
    "    cir += UN(SWAP, maps_obj=[(5, 13), (6, 14), (7, 15), (8, 16)])\n",
    "    cir += shift(ModMulti1xmod15Rev(), ns)\n",
    "\n",
    "    cir += UN(X, maps_obj=[4, 4], maps_ctrl=[2, 3])\n",
    "    cir += shift(ModMulti1xmod15(), ns)\n",
    "    cir += UN(SWAP, maps_obj=[(5, 13), (6, 14), (7, 15), (8, 16)])\n",
    "    cir += shift(ModMulti1xmod15Rev(), ns)\n",
    "\n",
    "    cir += X(4, 3)\n",
    "    return cir\n",
    "\n",
    "\n",
    "def demo4():\n",
    "    \"\"\"验证模指数器\n",
    "    \"\"\"\n",
    "    # 计算 7^a mod n\n",
    "    print(\"验证模指数器(8U32G硬件大约耗时20分钟):\")\n",
    "    a = 3\n",
    "    n = 15\n",
    "    cir_a = c2q([3, 2, 1, 0], a)\n",
    "    cir_n = c2q([25, 24, 23, 22], n)\n",
    "    cir_expmod = cir_a + cir_n + ModExp() + cir_n\n",
    "\n",
    "    q_res = q2c(cir_expmod, [8, 7, 6, 5])\n",
    "    c_res = (7**a) % n\n",
    "\n",
    "    print(f\"q_res = {q_res}, c_res = {c_res}\\n\")\n",
    "\n",
    "\n",
    "demo4()\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "94fb02d9-c47f-4045-9424-6ea5a9b6db66",
   "metadata": {},
   "source": [
    "其输出如下：\n",
    "\n",
    "```text\n",
    "验证模指数器(8U32G硬件大约耗时20分钟):\n",
    "ket string: 1¦000000000000000000110100011⟩\n",
    "q_res = 13, c_res = 13\n",
    "```\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "a8bdf0be-529e-45a3-96ce-fa1c94741095",
   "metadata": {},
   "source": [
    "## 总结\n",
    "\n",
    "该教程使用 MindQuantum 实现了 VQE 方法的 4-bit 加法器、减法器、模乘法器和模指数器。模指数器是Shor算法重要组成部分，也是搭建加法器、模乘法器等的最终目标。文中提出的线路实现没有考虑优化，当前文献中已经有一些其他更高效的实现方法，例如使用半经典的傅里叶变换、基于QFT的线路等等实现模指数运算器。\n",
    "\n",
    "## 参考文献\n",
    "\n",
    "[H. T. Larasati and H. Kim, \"Simulation of Modular Exponentiation Circuit for Shor's Algorithm in Qiskit, 2020](https://ieeexplore.ieee.org/document/9310794)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "mindspore",
   "language": "python",
   "name": "mindspore"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6 (tags/v3.8.6:db45529, Sep 23 2020, 15:52:53) [MSC v.1927 64 bit (AMD64)]"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
